As described in the above-referenced co-pending application, many color image processing systems employ a reduced complexity (low cost) output (display) device that accesses a relatively small data resolution image frame buffer to define the contents of the displayed image. Namely, the image frame buffer has a storage capacity (typically on the order of eight bits per pixel), which is considerably less than that necessary to accommodate the encoding resolution (e.g. twenty-four bits per pixel) into which an original color image has been digitized by a color opto-electronic imaging device, such as a high precision digitizing color camera. Since the output (e.g. color display) device usually has a resolution of eight bits per color at the input of each of three respective digital-to-analog converters which drive its red, green and blue signal ports, it is possible for the output device to replicate any of the colors within the original image, as long as a code representative of that particular color is stored in the frame buffer.
Unfortunately, the limited capacity of an eight bit frame buffer means that only 256 color codes, out of the approximately 16 million possible colors codes available to define the original digital color image, can be stored in the frame buffer. As a consequence, it is necessary to employ a color conversion mechanism through which each of the colors of the original input digitally encoded image (e.g. out of a possibility of 2.sup.24 =1.6.times.10.sup.7 colors) is effectively transformed, or quantized, into one of a lesser number of output colors (e.g. 2.sup.8 =256 colors) for driving the display device.
Color quantization has been the fundamental technique for reducing the color code resolution of the original color image size to a limited palette of color codes that can be accommodated by a limited code resolution frame buffer, and which are selected to as faithfully as possible replicate the color characteristics of the original image. Color quantization typically has involved the use of some form of vector quantization and operates to minimize an objective error criterion (usually mean squared error).
One class of quantization techniques, as described in articles by P Heckbert, entitled "Color image quantization for frame buffer display," Computer Graphics, Vol. 16, No. 3, pp 297-307, July 1972, G. Braudaway, entitled "A procedure for optimum choice of a small number of colors from a large color palette for color imaging," Electronic Imaging `87, San Francisco Calif., 1987 and R. Gentile et al entitled "Quantization of color images based on uniform color spaces," Journal of Imaging Technology, Vol. 16, No. 1, pp 12-21, February 1990, selects an initial color palette and iteratively refines this palette, using the algorithm described in an article by Y. Linde et al, entitled "An algorithm for vector quantizer design," IEEE Transactions on Communications, Vol. COM-28, pp 84-95, January 1980. While these vector quantization mechanisms yield high quality images, they are very computationally intensive.
Another approach involves generating a set of color clusters and using the centroids of the clusters as palette colors. This scheme is described, for example, in an article entitled "Quantization of color images for display/printing on limited color output devices," by S. S. Dixit, Comput. & Graphics, vol. 15, no. 4, pp. 561-567, 1991, and in an article by R. Balasubramanian et al, entitled "A new approach to palette selection for color images," Journal of Imaging Technology, Vol. 17, No. 6, pp. 284-290, December 1991, and is based upon a clustering vector quantization technique proposed in an article by W. Equitz entitled "A new vector quantization algorithm," IEEE Transactions on Acoustics, Speech, Signal Processing, Vol. 37, No. 10, pp 1568-1575, October 1989.
In accordance with this clustering approach, all of the colors of an image are grouped into `clusters`, by merging nearest neighbor pair of clusters, one at a time, until the number of clusters equals the desired number of palette colors. The centroids of the clusters are selected as the palette colors. Tree structures are used to perform efficient nearest neighbor searches. In addition, this scheme employs histogramming to reduce the number of initial colors and a spatial activity weighting to take into account the sensitivity of the human visual system to quantization errors in relatively `smooth` regions of the image.
A third class of vector quantization algorithms uses `splitting` techniques to divide or `split` the color space into smaller sub-regions and selects a representative palette color from each sub-region. In general, splitting techniques are computationally more efficient than either of the iterative or merging techniques and can provide a structure to the color space that enables efficient pixel mapping at the output.
One of these splitting techniques, termed a `median cut` algorithm and described, for example, in an article by P. Heckbert, entitled "Color image quantization for frame buffer display," Computer Graphics, vol. 16, no. 3. pp. 297-307, July 1982, recursively splits a region into two sub-regions by locating a plane perpendicular to the coordinate axis having the greatest range (where the range is the difference between the maximum and minimum values of that coordinate) and which passes through the median point of that coordinate axis.
A second splitting technique is a variance-based algorithm which splits the region having the largest total squared error (TSE). Data points are projected onto each of the coordinate axes and the projected TSEs computed. The region is then split along that axis yielding the smallest sum of projected TSEs from the two resulting sub-regions. For a detailed discussion of the variance splitting algorithm attention may be directed to an article by S. Wan et al, entitled "Variance based color image quantization for frame buffer display", COLOR Research and Applications, Vol. 15, No. 1, pp 52-58 February 1990.
A third splitting algorithm, which is the most optimal in a quantitative sense, is the binary splitting algorithm. The binary splitting algorithm passes a splitting plane through the centroid of all the colors of the region, such that the splitting plane is oriented perpendicular to the direction of maximum total squared variation. The latter is derived from the principal eigenvalue and eigenvector of the covariance matrix of the data in that region. At each step the region to be split is that with the largest associated principal eigenvalue. The binary splitting algorithm also incorporates spatial activity measures to enhance the subjective quality of the image. For a detailed discussion of the binary splitting algorithm attention may be directed to an article by M. Orchard et al, entitled "Color quantization of images", IEEE Transactions on Signal Processing Vol. 39, No. 12, pp 2677-2690, December 1991, and the U.S. patent to Bouman et al, U.S. Pat. No. 5,047,842, issued Sep. 10, 1991, entitled "Color Image Display with a Limited Palette Size."
In our above-referenced co-pending application, we describe a sequential product code vector quantization technique that incorporates the binary splitting technique, as part of the overall color code transformation process, for quantizing chrominance and luminance features of an image, based upon a conditional distribution of these features within partitioned regions of chrominance/luminance color space. Advantageously, this sequential product code scheme yields a set of reduced codewidth input, coordinate conversion look-up tables which, when cascaded together, yield a transform operator that rapidly converts the color value of each pixel of an original image into an output image color code, the output image color code both closely matching the color of the original image and being spatial activity dependent, so as to prevent the generation of contouring artifacts in the reproduced image.
The operation of the binary splitting-based sequential product code vector quantization mechanism described in our above-referenced co-pending application may be understood by reference to FIGS. 1-5, which contain a reduced complexity illustration of three dimensional axial splitting of a YCC (Y,Cr,Cb) color space along its respective axes into respective color space cells, corresponding identity codes for which yield an intended output color code palette.
Referring initially to FIG. 1, a three dimensional rectangular coordinate color space distribution (histogram) of luminance and chrominance components of an image, defined in terms of a luminance axis Y, and a pair of chrominance axes Cr and Cb mutually orthogonal to one another and to the luminance axis Y, is diagrammatically illustrated as having the shape of a histogram cube 21. Namely, in the present example, cube 21 is considered to contain the entire color space distribution of all of the luminance and chrominance components that define the image of interest. The objective of the binary splitting mechanism is to sequentially quantize this color space distribution into a reduced set of respective color codes of a `palette` that will produce an output color image having a high quality that is pleasing to the human visual system (HVS). For this purpose, the color space cube 21 is subject to a sequence of binary splits along each of its respective axes to produce a set of rectangular solid-shaped color space cells or blocks, the respective sides of which are defined by respective splits that are orthogonal to the three axes (Y,Cr,Cb).
Let it be initially assumed that the number of splits allowed is a relatively small number such that the original color space is to be split twice (into three slices) along the Cr axis, each of the three resulting slices of the (Cr axis-partitioned) color space is to be split once along the Cb axis, and each of the six resulting columns of the (Cr and Cb axis-partitioned) color space is to be split twice along the Y axis. It should be observed that the number and locations of the splits in the present example are merely for purposes of illustration and each constitutes an arbitrary choice. It should also be noted that, in a practical application, it is not always the case that every partitioned subcomponent (slice, column) of the original color space will be further partitioned. (In a practical image, for an eight bit display buffer, the total number of quantization levels is 256, where each of the two chrominance axes has a relatively small number of quantization partitions (e.g. on the order of eight splits each), with the vast majority of quantization partitions (well over 200) lying along the luminance axis, because of the greater sensitivity of the human visual system to luminance variations than to chrominance variations.)
In the present example of splitting the Cr axis first, followed by splitting along the Cb axis, the original color space cube of FIG. 1 is subdivided or partitioned along Cr axis split planes SP1, SP2 into three parallel slices 31, 32 and 33, as diagrammatically illustrated in FIG. 2, with each split plane SPi being orthogonal to the respective axis being split. (It should be noted that were the original color space of FIG. 1 subjected to a single split along the Cb axis prior to partitioning along the Cr axis, then the cube of FIG. 1 would be subdivided or partitioned as diagrammatically illustrated in FIG. 3 along a single split plane SP3 into two parallel slices 41 and 42.)
For the present example of splitting the color space cube of FIG. 1 along the Cr axis first, followed by a splitting each of the resulting slices along the Cb axis, then, as diagrammatically illustrated in FIG. 4, each of the three slices 31, 32, 33 of FIG. 2 will be partitioned along split planes SP4, SP5 and SP6 into two sub-slices or columns, yielding a total of six columns: 31-1, 31-2; 32-1, 32-2; and 33-1, 33-2. It should be noted that although each split plane SP4, SP5, SP6 subdivides a respective slice 31, 32, 33 into sub-slices, the locations of the splits are not necessarily and are not expected to be coplanar with one another. Moreover, as noted previously, in any image application, the splitting mechanism will not necessarily effect a partitioning or split through each slice. The location of each respective split plane is based upon an evaluation of the particular color space being split by that split plane, such that the splitting plane passes through the centroid of all the colors of the color space region being split.
As discussed above, for the case of an initial single split of the original color space cube 21 of FIG. 1 by way of the Cb axis split plane SP3 of FIG. 3, the color space being split is the entire cube, so that the location of a split plane SP3 is based upon an evaluation of the color space distribution of the entire color space cube 21. Once the cube 21 has been subdivided into slices, however, the location of each subsequent split of the resulting slices will depend upon the color space contents of each respective slice, not the original color space cube 21. Thus, a dual axis splitting of the original color space cube 21, along the Cb axis first, followed by the Cr axis, will produce a different set of sub-slices or columns than that shown in FIG. 4, thereby changing the composition of the color space palette that will be obtained after the third and final split along the Y axis.
In accordance with the sequential quantization methodology described in out co-pending application, which of the two chrominance axes (Cr, Cb) is chosen to begin the sequential splitting process is that chrominance axis which, when split, realizes a larger reduction in total squared error. The criterion used to determine the sequential order of partitioning of the axis is equal to the product of the number of data values projected upon the segment of the axis to be split and the variance of the data along that segment of the axis. That axis segment having the largest splitting criterion is split first. After a segment has been split into two sub-segments, respective splitting criteria are then computed for the sub-segments and compared with the splitting criteria for all other segments of the axis. Again, whichever segment (or sub-segment) of the axis has the largest splitting criterion is split next. This process is repeated either until the axis has been partitioned into the number of splits initially assigned to it.
For the illustrative example of FIG. 4, which depicts the result of splitting the original color space cube 21 of FIG. 1 into three slices along the Cr axis first, followed by a split of each of the three resulting slices into six color space columns along the Cb axis, a third and final split of the distribution of the columns of FIG. 4 along the Y axis is diagrammatically illustrated in FIG. 5. In the present example of splitting each of the six columns of FIG. 4 twice, there are twelve splits SP7-SP17, shown in FIG. 5, producing a total of eighteen cells or blocks: 31-1-1, 31-1-2, 31-1-3, 31-2-1, 31-2-2, 31-2-3, 32-1-1, 32-1-2, 32-1-3, 32-2-1, 32-2-2, 32-2-3 , 33-1-1, 33-1-2 , 33-1-3 , 33-2-1, 33-2-2 and 33-2-3. Again because the location of the splits of an individual column is based upon an evaluation of the color space distribution of the columns resulting from the immediately preceding split (along the Cb axis in the present example), the locations of the pairs of splits of each of the columns can be expected to be different for the respective columns.
Because of the increased sensitivity of the human visual system to low spatial activity, the splitting criterion along the luminance (Y) axis is weighted in inverse proportion to the average spatial activity of the region subject to be split. The number of splits along each respective axis determines the number of cells or blocks into which the histogram color space is subdivided, and thereby determines the number of colors of the palette. As noted above, for an eight bit display buffer, the total number of available palette codes is 256; each of the chrominance axes may be split at seven or eight locations, while there may be on the order of 240 splits of the partitioned chrominance regions into luminance-chrominance subregions. This large number of splits along the luminance axis has been found to effectively eliminate objectionable contouring artifacts, thereby resulting in a high quality image that is pleasing to the human visual system. After the quantization of the color space, the luminance and chrominance codes are reconverted back into respective R, G and B code values. A video memory in which palette color labels are stored may be coupled to a look-up table which generates RGB values associated with the palette color labels.